package paixu;

public class Qsort {
    public static void main(String[] args) {
//        int arr [] = new int[]{3,2,6,5,8,4,1};
        int arr [] = new int[8000000];
        for (int i = 0;i<8000000;i++){
            arr[i]= (int) (Math.random()*8000000);
        }
        long l = System.currentTimeMillis();
        sort(arr,0,arr.length-1);
        long l1 = System.currentTimeMillis();
        System.out.println(l1-l);
//        System.out.println(Arrays.toString(arr));
    }
    public static void sort(int [] arr,int left,int right){
        int l = left;
        int r = right;
        int poivet = arr[(left+right)/2];
        while (l<r){
            //找比中间大的值
            while (arr[l] < poivet){
                l+=1;
            }
            //找比中间小的值
            while(arr[r] > poivet){
                r-=1;
            }

            int temp = arr[l];
            arr[l]=arr[r];
            arr[r]=temp;
            //当l>=r时 表示已经排序完成
            if(l>=r){
                break;
            }
        //下面两个循环是防止出现两个相同元素时 出现死循环
            if(arr[l]==poivet){
                r-=1;
            }
            if(arr[r]==poivet){
                l+=1;
            }
        }
        //如果循环出来时l==r 要错位 否则会栈溢出
        if(l==r){
            l+=1;
            r-=1;
        }
        //[0-r]范围
        if (left<r){
            sort(arr,left,r);
        }
        //[l- arr.lenght]范围
        if (right>l){
            sort(arr,l,right);
        }
    }
}
